package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class fifteen {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list=new ArrayList<>();
        int m=s.length();
        int n=words.length;
        int p=words[0].length();
        if(m<n*p){
            return list;
        }
        HashMap<String,Integer> hashmap=new HashMap<>();
        for(int i=0;i<n;i++){
            String in=words[i];
            hashmap.put(in,hashmap.getOrDefault(in,0)+1);
        }
//        HashMap<String,Integer> hashmap1=new HashMap<>();
        int left;
        int right;
        int count=0;
        //处理滑动窗口执行的次数
        for(int i=0;i<p;i++){
            HashMap<String,Integer> hashmap1=new HashMap<>();
            for(left=0,right=0;right+p<m;right+=p){
                String in1=s.substring(right,right+p);
                hashmap1.put(in1,hashmap1.getOrDefault(in1,0)+1);
                count++;
                if(count==n){
                    if(hashmap.equals(hashmap1)){
                        list.add(left);
                    }
                    String out=s.substring(left,left+p);
                    hashmap1.put(out,hashmap1.get(out)-1);
                    if(hashmap1.get(out)==0){
                        hashmap1.remove(out);
                    }
                    left+=p;
                    count--;
                }
            }

        }
        return list;

    }

    public static void main(String[] args) {
//        s = "barfoothefoobarman", words = ["foo","bar"]
        String s="barfoothefoobarman";
        String[] words={"foo","bar"};
        List<Integer> substring = findSubstring(s, words);
        System.out.println(substring);


    }
}
